//
// Created by 11510 on 2024/6/28.
//
#include <stdio.h>
#include <string.h>
#include <stdlib.h>



typedef struct {
    int key[200010];
    int value[200010];
    int left[200010];
    int right[200010];
    int idx;
    int head, tail;
}LinkedList;



void CreateLinkedList(LinkedList* list) {
    list->idx = 2;
    list->head = -1;
    list->tail = -1;
}
void _Link(LinkedList* list, int x, int y) {
    list->right[x] = y;
    list->left[y] = x;
}
void add_behind_tail(LinkedList* list, int k, int v) {
    list->key[list->idx] = k;
    list->value[list->idx] = v;

    list->left[list->idx] = -1;
    list->right[list->idx] = -1;

    if (list->head == -1) {
        list->head = list->tail = list->idx;
    } else {
        _Link(list, list->tail, list->idx);
        list->tail = list->idx;
    }
    list->idx++;

}
void remove_head(LinkedList* list) {
    if(list->head == list->tail){
        list->head = list->tail = -1;
    } else {
        list->key[list->head] = -1;
        list->value[list->head] = -1;
        list->head = list->right[list->head];
        list->left[list->head] = -1;
    }
}
void remove_tail(LinkedList* list){
    if(list->head == list->tail){
        list->head = list->tail = -1;
    }else{
        list->tail = list->left[list->tail];
        list->right[list->tail] = -1;
    }
}
void remove_node_by_address(LinkedList* list, int node) {
    if(node == list->head){
        remove_head(list);
    }else if (node == list->tail){
        remove_tail(list);
    }else {
        _Link(list, list->left[node], list->right[node]);
    }
}



LinkedList linkedList;
typedef struct {
    int hashTable[11000];
    int size;
    int capacity;
} LRUCache;


LRUCache* lRUCacheCreate(int capacity) {
    LRUCache * lruCache = (LRUCache*)malloc(sizeof (LRUCache));
    memset(lruCache->hashTable, -1, sizeof(int) * 11000);
    CreateLinkedList(&linkedList);

    lruCache->size = 0;
    lruCache->capacity = capacity;
    return lruCache;
}

int lRUCacheGet(LRUCache* obj, int key) {
    int address = obj->hashTable[key];

    if(address != -1){
        int k = linkedList.key[obj->hashTable[key]];
        int v = linkedList.value[obj->hashTable[key]];

        /* move to end */
        remove_node_by_address(&linkedList, obj->hashTable[key]);
        add_behind_tail(&linkedList, k, v);
        obj->hashTable[key] = linkedList.tail;

        return v;
    }

    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    add_behind_tail(&linkedList, key, value);

    if (obj->hashTable[key] != -1) {
        /* 覆盖 */
        remove_node_by_address(&linkedList, obj->hashTable[key]);
        obj->hashTable[key] = linkedList.tail;
        return;
    }

    obj->hashTable[key] = linkedList.tail;
    obj->size++;

    if (obj->size > obj->capacity) {
        /* 头删 */
        int k = linkedList.key[linkedList.head];
        remove_head(&linkedList);
        obj->hashTable[k] = -1;
        obj->size--;
    }
}

void lRUCacheFree(LRUCache* obj) {
    free(obj);
    obj = NULL;
}






int main() {

    return 0;
}
